1. Field of the Invention
The present invention relates to a directional flooding method in a wireless sensor network in which packets transferred between respective nodes are induced toward a destination direction through directional information, thus obviating transmission of unnecessary packets to allow for efficient transmission of the packets.
2. Background of the Related Art
A wireless sensor network recently attracts academic interests due to its several unique characteristics different from a wireless ad hoc network. For example, in the wireless sensor network, a great number of sensor nodes having very limited energy and computing resources are crowded to form a network. Furthermore, each of the sensor nodes usually does not have a global identification such as an IP address.
The wireless sensor network is, however, still considered as a kind of the ad hoc wireless network. This is because the two networks are very similar in terms of various points. For instance, the sensor network and the ad hoc network are self-configured and self-maintained independently without intervention from the outside. They are also similar in that transmission of packets is accomplished through multi-hop of a wireless link (multi-hop routing). In the mobile ad hoc network, researches on a routing protocol have been actively made. There already exist several protocols.
On the contrary, in the wireless sensor network, lots of attention to routing from a sensor node to a sink node (data dissemination) has recently been paid. In the above, the sink node refers to a node that transfers data sensed in the sensor network to a person, or is connected to a base network to transfer data.
Routing methods in the wireless ad hoc network or the wireless sensor network are mostly based on flooding. They have a problem that the cost is high. Furthermore, in most MAC protocols used in the mobile ad hoc network and the wireless sensor network, CSMA/CA for sensing carriers and supporting multiple access of a medium in order to avoid collision is used. Thus, if several neighboring nodes broadcast at the same time, the network can fall into a severe contention state. Broadcasting that is unnecessarily overlapped with this contention state and collision of signals may cause a broadcast storm problem.
Therefore, this simple flooding scheme needs to be improved in a more effective manner. In the ad hoc network environment, researches for solving this problem have been made and several algorithms have been proposed. Ideas on which these algorithms are based are to form an optimal broadcast tree so that packets can be transferred from a source to all nodes within the network.
However, the method of forming this optimal tree may be improper since unnecessary overhead is generated in the wireless sensor network environment. This is because data packets need not to be transmitted to all nodes within the network in the sensor network. In particular, it is sufficient that data sensed by common sensors are usually transmitted to a single destination node, i.e., only a sink node.
It will be examined how the methods that are searched so far in the mobile ad hoc network environment for more efficient flooding can be optimal solutions even in the wireless sensor network.
For example, in order to minimize defects of flooding called the broadcast storm, several methods in which the simple flooding method is modified a little have been proposed under an ad hoc network environment. Most of these methods are for minimizing the number of packets transmitted in the whole flooding process on the basis of ideas that an optimal broadcast tree is generated.
A method of simply flooding all the nodes and a method of using an optimal flooding tree will now be compared with reference to FIG. 1.
As shown in FIG. 1(a), if a simple flooding scheme is used, all nodes have to send packets in order to transmit packet once. Such a simple flooding scheme can transmit the packet very reliably, but requires high cost. For example, in FIG. 1(a), a total of 25-packet transmissions occurs.
For more efficient flooding, it is required that an optimal broadcast tree be found in order to minimize the number of packets transmitted. Even in this case, the packet sent by the source node can be still transferred to all the nodes. In FIG. 1(b), only 12 transmissions are required in order to transmit the packets to all the nodes.
However, a document “W. Liang” constructing Minimum-Energy Broadcast Trees in Wireless Ad Hoc Networks, “in proc. of ACM Mobihoc '02, pp. 112-123, June 2002.” demonstrates that a problem to find such an optimal broadcast tree is NP-complete. Accordingly, for an efficient flooding method, an alternative solution capable of forming a form close to the optimal broadcast tree was proposed.
For example, there were proposed a method in which an intermediate node determines whether to broadcast a packet again with a predetermined probability, a method in which the intermediate node uses a pre-calculated coverage and a method in which the intermediate node selectively floods by determining whether to transmit a packet using information on neighboring nodes. These methods have their objects to form a tree that can be broadcast more efficiently using an adaptive and heuristic algorithm.
Meanwhile, in the wireless sensor network, it is highly probable that the flooding method for forming this optimal broadcast tree cannot be the most effective flooding method. Forming the optimal broadcast tree is for meeting a premise that the packet has to be transferred to all the nodes in the network. This is because the premise itself is unnecessary in the wireless sensor network.
The purpose of flooding in the wireless sensor network is not to transfer the packet to all the nodes but to a single or several destination nodes like Unicast or Geocast. This means that transmission of the packet using the flooding method may have the directivity toward a specific destination node.
FIG. 2 shows a tree formed by a directional flooding method. In order to transmit a packet from a source node to a destination node, only four transmissions are enough.
Documents [C. Intanagonwiwat, R. Govinda, D. Estrin, and J. Heidemann, “Directed Diffusion for Wireless Sensor Networking,” in IEEE/ACM Transaction on Networking, Vol. 11, No. 1, pp. 2-16, February 2003], [F. Ye, G. Zhong, S. Lu, L. Zhang, “GRAdient Broadcast: A Robust Data Delivery Protocol for Large Scale Sensor Networks,” to appear at the ACM WINET Journal.], etc. disclose recent researches in association with efficient transmission of data in the wireless sensor network.
These methods determine whether to transmit the packet or not based on routing cost.
If the type of a network is frequently changed, however, these protocols require that information on neighboring nodes be updated on a regular basis. This may result in lots of overhead in the number of packets, energy consumption and delay.